// 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
// 使得 a + b + c = 0 ？
// 请你找出所有满足条件且不重复的三元组。

function threeSum(nums: number[]): number[][] {
    const res: number[][] = [];// 结果数组
    nums.sort((a, b) => a - b);// 先对给定数组进行排序
    // 循环三指针算法
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            return res;
        }// 防止基点出现重复
        if (nums[i] === nums[i - 1]) {
            continue;
        }
        let left: number = i + 1;// 声明左指针
        let right: number = nums.length - 1;// 声明右指针
        while (left < right) {
            let sum: number = nums[i] + nums[left] + nums[right];// 总和
            if (sum === 0) {
                // 防止左指针重复解
                while (left < right && nums[left] === nums[left + 1]) {
                    left++;
                }// 防止右指针出现重复解
                while (left < right && nums[right] === nums[right - 1]) {
                    right--;
                }// 把当前组合加入结果数组
                res.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
};

// 这道题考察的其实是一个比较少用到的三指针循环算法
// 此外还有一个比较棘手的地方在于所有的结果不能重复
// 首先我们对这个数组进行排序，因为有序这个性质对我们指针的划动判断而言重要
// 三指针算法中的三个指针分别指基点（数最小，位置最左，不移动）、左指针（中间位置）、右指针（右位置）
// 方式其实也很直接，我们先在单次循环中固定一个基点，
// 如果基点比 0 大就直接返回结果数组（因为数组是有序的，基点都大于0了那后面的数字肯定也是大于0，三个大于0数之和必定大于0）
// 然后左指针为基点下标+1，右指针为最右下标
// 依次根据三数之和来判断左右指针的移动情况
// 如果和小于零，那么就移动左指针往右
// 如果和大于零，那么就移动右指针往左
// 满足条件就把这三个指针对应数组加入结果数组中
// 这样就完成了一个基本的逻辑框架
// 但这里题目要求解不能重复，
// 所以需要分别在判准前确保基点、左指针、右指针都已经取到了唯一值且后面在滑动过程中不会出现重复
// 上述步骤验证即可。
